package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-07 15:10
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 零钱兑换2 {

    // 完全背包问题 一个数可以选择无限次
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] newCoins = new int[coins.length + 1];
        for (int i = 1; i <= n; i++) {
            newCoins[i] = coins[i - 1];
        }
        // 状态数组
        int[] f = new int[amount + 1];
        Arrays.fill(f,0);
        f[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = newCoins[i]; j <= amount; j++) {
                f[j] += f[j-newCoins[i]];
            }
        }
        return f[amount];
    }

}
